package org.example.SolutionNew003;

import java.util.LinkedList;
import java.util.Queue;

public class DoubleTree004 {
    public static void main(String[] args) {
        DoubleTree004 dt = new DoubleTree004();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        root.left.right = new TreeNode(3);
        System.out.println(dt.isSymmetric(root));
    }

    public boolean isSymmetric1(TreeNode root) {
        if (root == null) return true;
        TreeNode tempRight=invertTree(root.right);
        TreeNode left=root.left;
        TreeNode right=tempRight;
        return IsSame(left,right);
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    public boolean IsSame(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if(left == null || right == null) return false;
        boolean leftIsSymmetric = true;
        boolean rightIsSymmetric = true;
        leftIsSymmetric=IsSame(left.left,right.left);
        rightIsSymmetric=IsSame(right.right,left.right);
        return leftIsSymmetric && rightIsSymmetric && left.val == right.val;
    }

    //优化，不用翻转
    public boolean isSymmetric2(TreeNode root) {
        return check2(root.left,root.right);
    }

    private boolean check2(TreeNode left,TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return left.val==right.val && check2(left.left,right.right)&&check2(left.right,right.left);
    }

    //迭代 层序
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return check(root.left,root.right);
    }

    private boolean check(TreeNode left,TreeNode right) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(left);
        queue.add(right);

        while (!queue.isEmpty()) {
            left=queue.poll();
            right=queue.poll();

            if(left==null && right==null) continue;

            if((left == null || right == null)||left.val!=right.val) return false;

            queue.add(left.left);
            queue.add(right.right);

            queue.add(left.right);
            queue.add(right.left);
        }
        return true;
    }
}
